package sort

func SelectionSort(data []int) {
	if data == nil || len(data) <= 1 { // 边界
		return
	}

	// 循环不变量: data[0,i) 有序, data[i, n) 无序
	for i, n := 0, len(data); i < n; i++ {
		minIndex := i
		// 选择[i,n)中最小的元素
		for j := i + 1; j < n; j++ {
			if data[j] < data[minIndex] {
				minIndex = j
			}
		}
		// 完成排序的动作, 基于交换
		data[i], data[minIndex] = data[minIndex], data[i]
	}
}

// SelectionSortReverse 循环不变量和正向排序相反
func SelectionSortReverse(data []int) {
	if data == nil || len(data) <= 1 {
		return
	}

	for i := len(data) - 1; i >= 0; i-- {
		maxIndex := i
		for j := i - 1; j >= 0; j-- {
			if data[j] > data[maxIndex] {
				maxIndex = j
			}
		}
		data[i], data[maxIndex] = data[maxIndex], data[i]
	}
}
